{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第十三章 元胞自动机（Cellular automata）\n",
    "\n",
    "Code examples from [Think Complexity, 2nd edition](http://greenteapress.com/wp/complexity2), Chapter 5 - 8\n",
    "\n",
    "Copyright 2016 Allen Downey, [MIT License](http://opensource.org/licenses/MIT)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function, division\n",
    "\n",
    "%matplotlib inline\n",
    "%precision 3\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import thinkplot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from thinkstats2 import RandomSeed\n",
    "RandomSeed(17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 0 维 CA（Zero-dimensional CA）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个独立的元胞概念上代表对一个孤立点变化的模拟，它的状态随时间变化。下面是一个 0 维元胞的特例。这里时间也是离散的步长。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 10 # 10个时间步\n",
    "x = np.zeros(n) # 先全置0\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义细胞发展规则。$x^{(n+1)} = (x^{(n)} + 1) \\mod 2$，这里 $n$ 表示第 $n$ 个时刻。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x[1] = (x[0] + 1) % 2\n",
    "x[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按规则发展，直至填满全部."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(2, 10):\n",
    "    x[i] = (x[i-1] + 1) % 2\n",
    "    \n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以这个 CA 模拟的就是在两个状态间来回闪烁。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 一维CA（One-dimensional CA）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1D 的 CA 用 1D 的数组来存放一个时刻的状态。那么全部时刻就要用 2D 的数组来显示。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = 5   # 只看5个时间步\n",
    "cols = 11  # 每个时间步是11位的状态\n",
    "array = np.zeros((rows, cols), dtype=np.int8)\n",
    "array[0, 5] = 1\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用 imshow 来显示 0|1 的状态。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_ca(array):\n",
    "    cmap = plt.get_cmap('Blues')   # Blues是一种配色表\n",
    "    plt.imshow(array, interpolation='none', cmap=cmap)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面这个2D数组就这么表示，1用蓝色，0用白色。这是初值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_ca(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在定义时间发展规则：\n",
    "$$\n",
    "x_i^{(n+1)} = (x^{(n)}_{i-1}+x^{(n)}_i+x^{(n)}_{i+1}) \\mod 2.\n",
    "$$\n",
    "这里要注意每一行的首尾两位如何特殊处理，相当于如何设置边界条件。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def step(array, i):\n",
    "    rows, cols = array.shape\n",
    "    for j in range(1, cols-1):\n",
    "        array[i, j] = sum(array[i-1, j-1:j+2]) % 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按这个规则发展一步。想一下这里的边界条件是什么？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "step(array, 1)\n",
    "plot_ca(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "继续发展直到填满："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(1, rows):   \n",
    "    step(array, i)\n",
    "\n",
    "plot_ca(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "是不是比你预计的复杂？毕竟这么简单的规则...这里的边界条件，其实是按死了两边始终为 0。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**练习:** 多整几行几列（注意行列是不是要匹配？总之，开始浪！）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k=500\n",
    "cols=2*k+1\n",
    "rows=k\n",
    "array = np.zeros((rows, cols), dtype=np.int8)\n",
    "array[0, k] = 1\n",
    "for i in range(1, rows):   \n",
    "    step(array, i)\n",
    "plot_ca(array)\n",
    "\n",
    "# 能找到规律么？ 但是其实这个规律很简单啊..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如此简单的规则，我们就能得到这样的分形图案。我们还可以进一步考虑初值的影响："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k=500\n",
    "cols=2*k+1\n",
    "rows=k\n",
    "array = np.zeros((rows, cols), dtype=np.int8)\n",
    "array[0, k] = 1\n",
    "array[0, 100] = 1\n",
    "array[0, -100] = 1\n",
    "for i in range(1, rows):   \n",
    "    step(array, i)\n",
    "plot_ca(array)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "倒也还好，看来初值不如规则敏感。这也正常啊。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 互相关（Cross correlation）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们现在需要一个简洁的方式来表述规则，同时，也需要一个更有效的算法，这两件事情往往是一致的。我们这里引入数组的位运算："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = 5   \n",
    "cols = 11  \n",
    "array = np.zeros((rows, cols), dtype=np.int8)\n",
    "array[0, 5] = 1\n",
    "for i in range(1, rows):\n",
    "    step(array, i)\n",
    "plot_ca(array)\n",
    "# 因为前面被我们玩坏了，这里恢复一下数据先."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "window = np.zeros(cols, dtype=np.int8)\n",
    "window[:3] = 1   # 定义一个所谓的windows数组，前三位规定为1\n",
    "print(window)    # 看一下windows\n",
    "print(array[4])  # 看一下当前第4个时刻状态(注意已回复)\n",
    "print(window * array[4]) # 这里的乘法是按对位乘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以刚才的求和和取模规则可以等价表示为："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(window * array[4]) % 2   \n",
    "# 这个把第4时刻的前三位发展到第5时刻, 实际对应的结果应该是第5时刻的第1位(有第0位)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "numpy 提供了将 window 右移 1 位的操作："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "window = np.roll(window, 1)\n",
    "print(window)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这样可以继续将第 2 位发展到下一个时刻："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sum(window * array[4]) % 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以如此重新书写规则："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def step2(array, i):\n",
    "    rows, cols = array.shape\n",
    "    window = np.zeros(cols)\n",
    "    window[:3] = 1\n",
    "    for j in range(1, cols-1):  # 这里还是应该-1吧\n",
    "        array[i, j] = sum(window * array[i-1]) % 2\n",
    "        window = np.roll(window, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一样的规则，一样的结果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = 5   \n",
    "cols = 11  \n",
    "array = np.zeros((rows, cols), dtype=np.int8)\n",
    "array[0, 5] = 1\n",
    "for i in range(1, rows):\n",
    "    step2(array, i)\n",
    "\n",
    "plot_ca(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个序列操作称为滑动点积（sliding dot product）或互相关（cross correlation）。Numpy提供了相应的基层操作，用以替代for循环，效率更高。参数`mode='same'`表示结果和输入数组长度一致。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def step3(array, i):\n",
    "    window = np.array([1, 1, 1])   # window只要如此定义\n",
    "    array[i] = np.correlate(array[i-1], window, mode='same') % 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "结果自然还是一样："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = 5   \n",
    "cols = 11  \n",
    "array = np.zeros((rows, cols), dtype=np.int8)\n",
    "array[0, 5] = 1\n",
    "for i in range(1, rows):\n",
    "    step3(array, i)\n",
    "\n",
    "plot_ca(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "既然我们已经提到位运算了，继续使用整数表示0或1是愚蠢的，更合理的是基于二进制形式： "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_table(rule):\n",
    "    \"\"\"Make the table for a given CA rule.\n",
    "    \n",
    "    rule: int 0-255 \n",
    "    \n",
    "    用整数 0-255（两位16进制整数）来表达规则\n",
    "    \n",
    "    returns: array of 8 0s and 1s\n",
    "    也就是8个0或1啦\n",
    "    \"\"\"\n",
    "    rule = np.array([rule], dtype=np.uint8)\n",
    "    table = np.unpackbits(rule)[::-1]\n",
    "    return table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = np.array([150], dtype=np.uint8)\n",
    "print(rule)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table = np.unpackbits(rule)[::-1] #将rule转成二进制, 注意要反转\n",
    "print(table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在我们可以用二进制表达 table："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table = make_table(150)\n",
    "print(table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在我们用 table 来描述规则，这是外部输入的认为规定. 这里对应的是从000-111的8个数的组合，之前三位累加再取模的规则实际对应是：\n",
    "```\n",
    "000 - 0\n",
    "001 - 1\n",
    "010 - 1\n",
    "011 - 0 \n",
    "100 - 1\n",
    "101 - 0\n",
    "110 - 0\n",
    "111 - 1\n",
    "```\n",
    "注意左右。也就是我们需要一种快速操作，能对0和1的二进制串，每三位到这个table中去快速查找对应的变化。或者说，假设连续三位二进制数为$d_{i-1}, d_i, d_{i+1}$\n",
    "则对应的变化是记录在table[$(d_{i-1}d_id_{i+1})_{10}$]的位置. 而\n",
    "$$\n",
    "(d_{i-1}d_id_{i+1})_{10} = 4 \\times d_{i-1} + 2 \\times d_i + d_{i+1} = \\mbox{correlate([$d_{i-1}, d_i, d_{i+1}$], [4, 2, 1])}\n",
    "$$\n",
    "因此我们对一个已有的规则，只需用[4,2,1]这个序列去做correlate，就可以在table中的对应位置读出每三位二进制数的对应规则. 同时, table也代表了规则，我们可以用它的逆序的10进制数来表达. 比如CA150，CA50，等等。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里我们用互相关的规则来表达相邻几位求和，比如 `[4, 2, 1]` 代表的就是截取相邻的二进制 3 位，而 150 则是核心运算之后的对应规则，通过查表对应来代替实际计算。这里 150 实际上对应的规则就是求和再取 2 的模。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "window = [4,2,1]\n",
    "corr = np.correlate(array[0], window, mode='same')\n",
    "print(array[0])\n",
    "print(corr)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里 `corr` 是 `array[0]` 和 `[4,2,1]` 的互相关，实际上是从 `array[0][1]` 开始做的，`array[0][1]` 的左邻居，自己和右邻居是 `000`，因此 \n",
    "```\n",
    "corr[1] = correlate(array[0][0:3], window)\n",
    "        = correlate(000, 421) = 0 = 000, \n",
    "```\n",
    "以此类推，\n",
    "```\n",
    "corr[5] = correlate(array[0][4:7], window)\n",
    "        = correlate(010, 421) = 2 = 010,\n",
    "corr[6] = correlate(array[0][5:8], window)\n",
    "        = correlate(100, 421) = 4 = 100 ...\n",
    "```\n",
    "本质上就是取了 `array[0]` 相邻三位的二进制表示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "而 150 代表规则中三位相加模 2，不需要直接计算，查 table 就可以。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(table)   # table是规则缩写150转成二进制再反转\n",
    "array[1] = table[corr]   # corr是[4,2,1]和array[0]的互相关\n",
    "print(array[1])   # 和之前一致."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "再次重写程序实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def step4(array, i):\n",
    "    window = np.array([4, 2, 1])  \n",
    "    corr = np.correlate(array[i-1], window, mode='same')\n",
    "    array[i] = table[corr]   # 规则是150，模2的意思"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "果然还是一样的规则，但效率更高。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rows = 5   \n",
    "cols = 11  \n",
    "array = np.zeros((rows, cols), dtype=np.int8)\n",
    "array[0, 5] = 1\n",
    "for i in range(1, rows):\n",
    "    step4(array, i)\n",
    "\n",
    "plot_ca(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "让我们将 CA1D 的基本操作都写成一个类 Cell1D.py："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Cell1D import Cell1D, Cell1DViewer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "制作规则 CA50："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t=make_table(50)\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "生成一个 CA1D 的模拟就很方便："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = 50   # 规则50...\n",
    "n = 10\n",
    "ca = Cell1D(rule, n)\n",
    "ca.start_single()\n",
    "ca.loop(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "显示输出也附带："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = Cell1DViewer(ca)\n",
    "viewer.draw()\n",
    "\n",
    "plt.savefig('chap05-1.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "之前的 CA150："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = 150\n",
    "n = 5\n",
    "ca = Cell1D(rule, n)\n",
    "ca.start_single()\n",
    "ca.loop(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = Cell1DViewer(ca)\n",
    "viewer.draw()\n",
    "\n",
    "plt.savefig('chap05-2.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "随便浪，规模也可以任意调整："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = 18\n",
    "n = 64\n",
    "ca = Cell1D(rule, n)\n",
    "ca.start_single()\n",
    "ca.loop(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = Cell1DViewer(ca)\n",
    "viewer.draw()\n",
    "\n",
    "plt.savefig('chap05-3.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "并不是所有的规则都是对称的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = 30\n",
    "n = 100\n",
    "ca = Cell1D(rule, n)\n",
    "ca.start_single()\n",
    "ca.loop(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = Cell1DViewer(ca)\n",
    "viewer.draw()\n",
    "\n",
    "plt.savefig('chap05-4.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "而 CA110 可以证明是图灵完备的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = 110\n",
    "n = 100\n",
    "ca = Cell1D(rule, n)\n",
    "ca.start_single()\n",
    "ca.loop(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = Cell1DViewer(ca)\n",
    "viewer.draw()\n",
    "\n",
    "plt.savefig('chap05-5.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "来个随机的大规模 CA110："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = 110\n",
    "n = 600\n",
    "ca = Cell1D(rule, n)\n",
    "ca.start_random()\n",
    "ca.loop(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = Cell1DViewer(ca)\n",
    "viewer.draw()\n",
    "\n",
    "plt.savefig('chap05-6.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 生命游戏（Game of life）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在需要装一个动画插件 ffmpeg，不然就没有动画了。尴尬的是，只支持Ubuntu，我不清楚 Windows 下是什么情况，似乎 ffmpeg 也是有的，但我不知道怎么装：\n",
    "\n",
    "    sudo add-apt-repository ppa:mc3man/trusty-media\n",
    "    sudo apt-get update\n",
    "    sudo apt-get install ffmpeg\n",
    "    \n",
    "我估计直接装源里的 ffmpeg 也可以。\n",
    "\n",
    "简单介绍一下由John Conway提出的生命游戏，Game of Life(GoL)，这是一种 2D 的图灵完备的元胞自动机。详细介绍见：\n",
    "\n",
    "[GoL](http://en.wikipedia.org/wiki/Conway_Game_of_Life)\n",
    "\n",
    "在 2D 的矩形网格上，每个格子有 0 或 1（代表死和生）两种状态。每个格子有 8 个邻居。在一步变化中，对每个活格子，若邻居的总和为 2-3，则此格子继续活，若邻居为0-1（太孤单），或4-8（太拥挤），则格子死。对每个死格子，若邻居为 3，则变活，其他情况继续死。如此简单的规则，却是图灵完备的，因此会有无穷尽的变化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import rc\n",
    "rc('animation', html='html5')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thinking Complexity 的作者提供了 Life.py 这个类，我们可以玩一下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 先直接用作者提供的Life.py实现。\n",
    "from Life import Life, LifeViewer\n",
    "\n",
    "# Life游戏是一个2D的CA，因此可以用两色的平面矩形网格表示一个时刻的状态。\n",
    "# 而不同时刻的状态变换就可以形成一个动画。\n",
    "def make_viewer(n, m, row, col, *strings):\n",
    "    \"\"\"Makes a Life and LifeViewer object.\n",
    "    \n",
    "    n, m: rows and columns of the Life array\n",
    "    \n",
    "    表达一个时刻的生命状态的网格是n行m列\n",
    "    \n",
    "    row, col: upper left coordinate of the cells to be added\n",
    "    \n",
    "    左上角的顶格的坐标\n",
    "    \n",
    "    strings: list of strings of '0' and '1'\n",
    "    \n",
    "    一列由‘0’和‘1’构成的字符串，表达生命的状态。应该注意和m、n要匹配。\n",
    "    \"\"\"\n",
    "    life = Life(n, m)   # n行m列的格子\n",
    "    life.add_cells(row, col, *strings)   # 左上角坐标\n",
    "    viewer = LifeViewer(life)   # 瞅一眼\n",
    "    return viewer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "蜂巢是一种稳定的生命模式，又称稳态的生命。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# beehive   蜂巢\n",
    "# 模式实际由01字串决定\n",
    "viewer = make_viewer(3, 4, 0, 0, '0110', '1001', '0110')\n",
    "viewer.draw(grid=True)\n",
    "plt.savefig('chap06-1.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "发展一步没有变化，所以称稳态。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer.step()\n",
    "viewer.draw(grid=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "蛤蟆是一个2周期振荡模式..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# toad   蛤蟆\n",
    "thinkplot.preplot(cols=2)\n",
    "viewer = make_viewer(4, 4, 1, 0, '0111', '1110')\n",
    "viewer.draw(grid=True)\n",
    "\n",
    "thinkplot.subplot(2)\n",
    "viewer.step()\n",
    "viewer.draw(grid=True)\n",
    "\n",
    "plt.savefig('chap06-2.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "再发展一步就回到初始状态。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer.step()\n",
    "anim = viewer.animate(frames=4, interval=400, grid=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果这里报错，那就是说你缺了ffmpeg，Ubuntu版本请参照开始，非Unix版本就呵呵了。动画能看到2周期振荡。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "滑翔机是一个4周期模式。但每变化一次，位置会朝下右前进一格。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# glider\n",
    "glider = ['010', '001', '111']\n",
    "\n",
    "thinkplot.preplot(cols=5)\n",
    "viewer = make_viewer(4, 4, 0, 0, *glider)\n",
    "viewer.draw(grid=True)\n",
    "\n",
    "for i in range(2, 6):\n",
    "    viewer.step()\n",
    "    thinkplot.subplot(i)\n",
    "    viewer.draw(grid=True)\n",
    "    \n",
    "plt.savefig('chap06-3.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们需要一个动画来显示滑翔机的移动。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = make_viewer(10, 10, 0, 0, '010', '001', '111')\n",
    "anim = viewer.animate(frames=32, interval=200, grid=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "r-pentomino 初始只有5个生命。但是经过1103步后，它居然会稳定。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# r pentomino\n",
    "rpent = ['011', '110', '010']\n",
    "\n",
    "viewer = make_viewer(3, 3, 0, 0, *rpent)\n",
    "viewer.draw(grid=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这是初始和稳定的状态。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# r pentomino\n",
    "rpent = ['011', '110', '010']\n",
    "\n",
    "thinkplot.preplot(cols=2)\n",
    "viewer = make_viewer(120, 120, 50, 45, *rpent)\n",
    "viewer.draw()\n",
    "\n",
    "for i in range(1103):\n",
    "    viewer.step()\n",
    "\n",
    "thinkplot.subplot(2)\n",
    "viewer.draw()\n",
    "plt.savefig('chap06-4.pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动画演示。最终是2周期稳态。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = make_viewer(120, 120, 50, 45, *rpent)\n",
    "anim = viewer.animate(frames=1200, interval=10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conway猜想\n",
    "\n",
    "Conway发现似乎所有模式最终都会进入一种稳态。那么是否有一种初值，能持续不断地产生无限多的活个体？Conway猜测不存在。但是他同时指出可能有两种情况导致他的猜想错误，一种是能持续飞出飞船的模式（他称为gun），还有一种是能将活个体从一个行走的模式中抛下。\n",
    "[puffer train](https://en.wikipedia.org/wiki/Puffer_train)\n",
    "\n",
    "这些模式不容易构建。Gosling第一次实现了gun模式。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "glider_gun = [\n",
    "    '000000000000000000000000100000000000',\n",
    "    '000000000000000000000010100000000000',\n",
    "    '000000000000110000001100000000000011',\n",
    "    '000000000001000100001100000000000011',\n",
    "    '110000000010000010001100000000000000',\n",
    "    '110000000010001011000010100000000000',\n",
    "    '000000000010000010000000100000000000',\n",
    "    '000000000001000100000000000000000000',\n",
    "    '000000000000110000000000000000000000'\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "初始状态长这样:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = make_viewer(11, 38, 1, 1, *glider_gun)\n",
    "viewer.draw(grid=True)\n",
    "plt.savefig('chap06-5.pdf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "viewer = make_viewer(50, 50, 2, 2, *glider_gun)\n",
    "anim = viewer.animate(frames=500, interval=20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 生命游戏的实现\n",
    "\n",
    "\n",
    "我们从一个随机矩阵开始："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = np.random.randint(2, size=(10, 10)).astype(np.uint8)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面这段代码低效，但人性。如果用 C 或 C++ 实现，就可以参照这个。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = np.zeros_like(a)   # 像a一样的0矩阵\n",
    "rows, cols = a.shape   # 取a的行列\n",
    "# 这里的循环避开了边界，只处理内部点\n",
    "for i in range(1, rows-1):\n",
    "    for j in range(1, cols-1):\n",
    "        state = a[i, j]   # 取a[i, j]状态\n",
    "        neighbors = a[i-1:i+2, j-1:j+2]   # 取a_ij的全部邻居\n",
    "        k = np.sum(neighbors) - state   # 求和，去掉自己\n",
    "        # 应用规则\n",
    "        if state:   \n",
    "            if k==2 or k==3:\n",
    "                b[i, j] = 1\n",
    "        else:\n",
    "            if k == 3:\n",
    "                b[i, j] = 1\n",
    "\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = np.zeros_like(a)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用互相关操作可以加速。但可读性就差了。而且注意，这里还处理了边界点，和上面只处理内部点是不同的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.signal import correlate2d\n",
    "\n",
    "kernel = np.array([[1, 1, 1],\n",
    "                   [1, 0, 1],\n",
    "                   [1, 1, 1]]) \n",
    "\n",
    "# 这里相当与a_ij为中心的9个格子做点积，再累加。a_ij遍历整个网格。边界之外算0。\n",
    "c = correlate2d(a, kernel, mode='same')   \n",
    "print(c)   # 多写一个c\n",
    "# 这句尤其没人性。&a表示若a是活的，由前面逻辑决定，若a是死的，必死。\n",
    "# &优先级高于|，故先判定 (c==2) & a，即c==3，必活。\n",
    "b = (c==3) | (c==2) & a \n",
    "b = b.astype(np.uint8)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果把kernel的中心改成10，我们可以简化这个逻辑。（增加死和活的分离，主要那个判定太恶心）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kernel = np.array([[1, 1, 1],\n",
    "                   [1,10, 1],\n",
    "                   [1, 1, 1]])\n",
    "\n",
    "c = correlate2d(a, kernel, mode='same')\n",
    "print(c)\n",
    "b = (c==3) | (c==12) | (c==13)\n",
    "b = b.astype(np.uint8)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "更重要的是我们又可以像1D CA那样，构建规则表了。（全或关系）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "table = np.zeros(20, dtype=np.uint8)\n",
    "table[[3, 12, 13]] = 1\n",
    "c = correlate2d(a, kernel, mode='same')\n",
    "b = table[c]\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:**  Start GoL in a random state and run it until it stabilizes.\n",
    "What stable patterns can you identify?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 大部分的随机初始会导致一堆的闪烁，块，蜂巢，少量的船，小艇和\n",
    "# （面包？都什么乱七八糟的...）\n",
    "# 还有人专门玩这个...\n",
    "# See Achim Flammenkamp, \"Most seen natural occurring ash objects in Game of Life\",\n",
    "# http://wwwhomes.uni-bielefeld.de/achim/freq_top_life.html)\n",
    "\n",
    "n, m = 100, 100\n",
    "life = Life(n, m)\n",
    "life.array = np.random.randint(2, size=(n, m)).astype(np.uint8)\n",
    "viewer = LifeViewer(life)\n",
    "anim = viewer.animate(frames=1000, interval=20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "很多地方提供了生命游戏的压缩模式，比如： http://www.conwaylife.com/wiki/Main_Page.\n",
    "\n",
    "写一个函数解析这些格式并作为初值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "\n",
    "# The easiest format to parse is plain text: \n",
    "# 最早的模式采用纯文本来描述：\n",
    "# 形参依次为：生命类，格式文件，行数，列数        \n",
    "def read_life_file(life, filename, row, col):\n",
    "    i = row\n",
    "    with open(filename) as f:   # 文本方式打开\n",
    "        for line in f:   # 对每一行\n",
    "            if line.startswith('!'):   # 若以！起头，是注释，跳过\n",
    "                continue \n",
    "            line = line.strip()   # 整行抓来，去掉首尾空格\n",
    "            line = line.replace('O', '1')   # 把0替换成1\n",
    "            line = line.replace('.', '0')   # 把.替换成0\n",
    "            life.add_cells(i, col, line)   #加入life实体\n",
    "            i += 1   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "\n",
    "# Here's an example that loads a period 52 oscillator.\n",
    "# http://www.conwaylife.com/w/index.php?title=35P52\n",
    "# 一个52周期的例子 \n",
    "\n",
    "n = 19\n",
    "m = 19\n",
    "row = 1\n",
    "col = 1\n",
    "\n",
    "life = Life(n, m)\n",
    "filename = '35p52.cells.txt'\n",
    "read_life_file(life, filename, row, col)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "# And here's the animation\n",
    "# 做个动画\n",
    "\n",
    "viewer = LifeViewer(life)\n",
    "anim = viewer.animate(frames=52, interval=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "\n",
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exercise: One of the longest-lived small patterns is rabbits'', which starts with 9 live cells and takes 17 331 steps to stabilize. You can get the initial configuration in various formats from http://www.conwaylife.com/wiki/Rabbits. Load this configuration and run it.\n",
    "\n",
    "最长的生命模式之一是大白兔，有9个活细胞，在达到稳态之前要经过17331步。这个初始配置在http://www.conwaylife.com/wiki/Rabbits 。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "\n",
    "# My solution to this exercise is in `LifeRabbits.py`.\n",
    "# The following command runs it in a separate process.\n",
    "\n",
    "# 作者提供了一个'LifeRabbits.py'的程序。\n",
    "\n",
    "rabbits = [\n",
    "        '1000111',\n",
    "        '111001',\n",
    "        '01'\n",
    "]\n",
    "\n",
    "n = 80\n",
    "m = 120\n",
    "life = Life(n, m)\n",
    "life.add_cells(n//2, m//2, *rabbits)\n",
    "viewer = LifeViewer(life)\n",
    "anim = viewer.animate(frames=400, interval=100)\n",
    "plt.subplots_adjust(left=0.01, right=0.99, bottom=0.01, top=0.99)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** In my implementation, the `Life` class is based on a parent class\n",
    "called `Cell2D`, and `LifeViewer` is based on `Cell2DViewer`.  You can\n",
    "use these base classes to implement other 2-D cellular automatons.\n",
    "\n",
    "在作者的程序中，Life类基于Cell2D而LifeViewer基于Cell2DViewer. 我们可以用这些基类来重新构建2D的元胞自动机。\n",
    "\n",
    "For example, one variation of GoL, called ``Highlife'', has the\n",
    "same rules as GoL, plus one additional rule: a dead cell with 6\n",
    "neighbors comes to life.\n",
    "\n",
    "例如，作为GoL一个变种，成为“高级生命”，比标准生命多了一条规则，当一个死亡细胞的邻居为6时，活跃。\n",
    "\n",
    "Write a class named `Highlife` that inherits from `Cell2D` and implements\n",
    "this version of the rules.  Also write a class named `HighlifeViewer`\n",
    "that inherits from `Cell2DViewer` and try different ways\n",
    "to visualize the results.  As a simple example, use a different\n",
    "color map.\n",
    "\n",
    "作者要求读者自行用Cell2D来实现新规则。并构建新的HighlifeViewer，同时换一种着色方式。\n",
    "\n",
    "One of the more interesting patterns in Highlife is the replicator.\n",
    "Use `add_cells` to initialize Highlife with a replicator and see what it\n",
    "does.\n",
    "\n",
    "高级生命最有趣的一种模式是复制器（replicator），实现并观察。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "from Cell2D import Cell2D, Cell2DViewer\n",
    "\n",
    "class Highlife(Cell2D):\n",
    "    \"\"\"Implementation of Highlife.\"\"\"\n",
    "    kernel = np.array([[1, 1, 1],\n",
    "                       [1,10, 1],\n",
    "                       [1, 1, 1]])\n",
    "\n",
    "    table = np.zeros(20, dtype=np.uint8)\n",
    "    table[[3, 6, 12, 13]] = 1   # 规则在这里变化。\n",
    "\n",
    "    def step(self):\n",
    "        \"\"\"Executes one time step.\"\"\"\n",
    "        c = correlate2d(self.array, self.kernel, mode='same')\n",
    "        self.array = self.table[c]\n",
    "        \n",
    "\n",
    "class HighlifeViewer(Cell2DViewer):\n",
    "    \"\"\"Viewer for Highlife.\"\"\"\n",
    "    cmap = plt.get_cmap('Purples')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "replicator = [\n",
    "    '00111',\n",
    "    '01001',\n",
    "    '10001',\n",
    "    '10010',\n",
    "    '11100'\n",
    "]\n",
    "\n",
    "n = 100\n",
    "life = Highlife(n)\n",
    "life.add_cells(n//2, n//2, *replicator)\n",
    "viewer = HighlifeViewer(life)\n",
    "anim = viewer.animate(frames=200)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "# 让人想起了什么？\n",
    "anim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exercise:\n",
    "\n",
    "If you generalize the Turing machine to two dimensions, or add a read-write head to a 2-D CA, the result is a cellular automaton called a Turmite. It is named after a termite because of the way the read-write head moves, but spelled wrong as an homage to Alan Turing.\n",
    "\n",
    "若是考虑2D的图灵机，或者给2D的CA加上读写头，那么这种自动机称为Turmite，这个专有名词融合了白蚁和图灵，前者是描述机器的行为，后者向图灵致敬。\n",
    "\n",
    "The most famous Turmite is Langton's Ant, discovered by Chris Langton in 1986. See http://en.wikipedia.org/wiki/Langton_ant.\n",
    "\n",
    "最有名的Turmite是Langton的蚂蚁，由Chris Langton在1986年提出，参见http://en.wikipedia.org/wiki/Langton_ant 。\n",
    "\n",
    "The ant is a read-write head with four states, which you can think of as facing north, south, east or west. The cells have two states, black and white.\n",
    "\n",
    "蚂蚁是一个读写头，并有4个状态。你可以将蚂蚁的头设置成朝北、南、东和西四个状态。每个格子有两个状态，黑或白。（注意细胞和格子在英语中可以是一个词。）\n",
    "\n",
    "The rules are simple. During each time step, the ant checks the color of the cell it is on. If black, the ant turns to the right, changes the cell to white, and moves forward one space. If the cell is white, the ant turns left, changes the cell to black, and moves forward.\n",
    "\n",
    "规则是简单的。每个时间不，蚂蚁会检查所在格子的颜色。如果是黑，则转右，并把格子变白，然后移动到下一个格子。如果是白，则转左，把格子变黑，并前进一个格子。\n",
    "\n",
    "Given a simple world, a simple set of rules, and only one moving part, you might expect to see simple behavior---but you should know better by now. Starting with all white cells, Langton's ant moves in a seemingly random pattern for more than 10 000 steps before it enters a cycle with a period of 104 steps. After each cycle, the ant is translated diagonally, so it leaves a trail called the \"highway\".\n",
    "\n",
    "简单的世界（网格），简单的规则（蚂蚁），每次只移动一步。你可能期待简单的行为。然而，对全白的网格，Langton的蚂蚁在10000步内几乎是在随机游走。最终会停留在一个104周期的振荡中。在每个周期，蚂蚁会转换对角（啥？），所以留下一条称为“高速公路”的小径（什么鬼！）。\n",
    "\n",
    "Write an implementation of Langton's Ant. 实现Langton的蚂蚁。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "from Turmite import Turmite, TurmiteViewer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "# Here's a small version that shows the first 20 steps:\n",
    "# 嗯，可爱的小蚂蚁...\n",
    "\n",
    "n = 5\n",
    "turmite = Turmite(n)\n",
    "viewer = TurmiteViewer(turmite)\n",
    "anim = viewer.animate(frames=20, interval=500, grid=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "# 看20步\n",
    "anim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here\n",
    "# 在网页下执行太花时间了，进入终端吧..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**作业：解读RLE格式\n",
    "\n",
    "在网站http://www.conwaylife.com/wiki/RLE 介绍了一种压缩的2D细胞机格式，在all.zip文件中包含了网站提供的全部细胞机模式。阅读网站（有pdf版本在群文件），解析并实现RLE文件为初值的细胞机机器演示。如无法动画就显示初值。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
